package me.zk.practice1.s;

import java.util.*;

/**
 * @author zhangkai
 * @date 2023/7/13 16:04
 */
public class LS_Offer_59 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        int i = 0;
        int j = k;
        while (j <= nums.length) {
            int maxnum = nums[i];
            for (int l = i+1; l < j; l++) {
                maxnum = Math.max(nums[l],maxnum);
            }
            list.add(maxnum);
            j++;
            i++;
        }
        int[] result = new int[list.size()];
        for (int l = 0; l < list.size(); l++) {
            result[l] = list.get(l);
        }
        return result;

    }
    public int[] maxSlidingWindow2(int[] nums, int k) {
        //优先级队列
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        //放入K个数
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{nums[i],i});
        }
        int[] res = new int[nums.length-k+1];
        res[0] = queue.peek()[0];
        for (int i = k; i < nums.length; i++) {
            queue.offer(new int[]{nums[i],i});
            while (queue.peek()[1]<=i-k){
                queue.poll();
            }
            res[i-k+1] = queue.peek()[0];
        }


        return res;
    }
    public int[] maxSlidingWindow3(int[] nums, int k) {
        //单调递减队列
        Deque<Integer> deque = new LinkedList<>();
        //返回数组
        int[] res = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {
            //单调递减一直移除队尾
            while (!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]) {
                //移除队尾数据
                deque.removeLast();
            }
            deque.add(i);
            //计算左边界
            int left = i-k+1;
            //当队列最大值不在左边界内后将其移除
            while (deque.peekFirst() < left) {
                deque.removeFirst();
            }
            if (i + 1 >= k) {
                res[left] = nums[deque.peekFirst()];
            }
        }


        return res;
    }


    public static void main(String[] args) {
        new LS_Offer_59().maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3);
    }
}
